package com.primary.linkedList;

import java.util.ArrayList;

/**
 * @author: yyh
 * @description:合并两个有序链表：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnnbp2/
 * @date: 2022/7/24 12:27
 */
public class MergeTwoLists {

    /**
     * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
     * <p>
     * 输入：l1 = [1,2,4], l2 = [1,3,4]
     * 输出：[1,1,2,3,4,4]
     * 示例 2：
     * <p>
     * 输入：l1 = [], l2 = []
     * 输出：[]
     * 示例 3：
     * <p>
     * 输入：l1 = [], l2 = [0]
     * 输出：[0]
     */
    ArrayList<ListNode> list = new ArrayList<>();

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        //1。先比较第一个，选择从哪个链表开始
        //2。选择的节点先跟自己next比较，next为空或不相等时再跟另一个链表比较
        //3。将小的设置为next，选择当前链表继续迭代

        //1->2->3->4
        //1->3->5
        ListNode current = list1.val < list2.val ? list1 : list2;
        ListNode other = list1 == current ? list2 : list1;

        ListNode first = current;
        ListNode tmp;
        while (true) {
            if (current.next != null) {
                if (current.val < current.next.val) {
                    if (current.next.val > other.val) {
                        tmp = current.next;
                        current.next = other;
                        other = tmp;
                        continue;
                        //1->'1'->3->5  '2'->3->4
                        //1->1->'2'->3->4  '3'->5
                        //1->1->2->'3'->4  '3'->5
                        //1->1->2->3->'3'->5  '4'->null
                        //1->1->2->3->3->'4'->null  '5''->null
                    }
                }
                current = current.next;
                //1->1->2->3->3->4->'5'->null
            } else {
                current.next = other;
                return first;
            }
        }
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
